package try01;
import java.util.*;

public class PermutationII {
	public void tester() {
		int [] a = {1,1,1,1,1,1,1,1,2,3,4,5,6,7};
		System.out.println(permuteUnique(a).size());
		
		
		
	}
	
	/*
	The idea of calculating size is: 1 1 2 2 3
	c(5,2) * c(5-2, 2) * c(5-2-2,1)
	 */
	public void calculateSize(int [] a) {
		ArrayList <Integer> al = new ArrayList <Integer>();
		int prev = -1;
		for(int i = 0 ; i < a.length ; i++) {
			if(i == 0) {
				prev = a[i];
				al.add(1);
			}
			else if(prev == a[i]) {
				al.set(al.size()-1, al.get(al.size()-1) + 1);
			}
			else {
				prev = a[i];
				al.add(1);
			}
		}
		int n = a.length;
		int RE = 1;
		for(int i = 0 ; i < al.size(); i++) {
			RE = RE * c(n, al.get(i));
			n = n - al.get(i);
		}
		System.out.println(RE);
	}
	
	public int c(int n, int a) {
		int result = 1;
		for(int i = n ; i >= n-a+1 ; i--) {
			result = result * i;
		}
		for(int i = a ; i > 0 ; i--) {
			result = result / i;
		}
		return result;
	}
	
List <List<Integer>> result = new ArrayList <List<Integer>>();
    
    public List<List<Integer>> permuteUnique(int[] num) {
        List <Integer> p1 = new ArrayList <Integer> ();
        List <Integer> p2 = new ArrayList <Integer> ();
        
        for(int i = 0 ; i < num.length ; i ++)
        {
            p1.add(num[i]);
        }
        
        Collections.sort(p1);
        
        p(p1, p2);
        return result;
    }
    
    public void p(List <Integer> p1, List <Integer> p2)
    {
        if(p1.size() == 0)
        {
            result.add(p2);
            for(int i = 0 ; i < p2.size(); i++) {
//            	System.out.print(p2.get(i)+" ");
            }
//            System.out.println();
            return;
        }
        
        int last = p1.get(0);
        for(int i = 0 ; i < p1.size() ; i ++)
        {
            List <Integer> p1t = clone(p1);
            List <Integer> p2t = clone(p2);
            if(i == 0 || p1.get(i) != last)
            {
                p2t.add(p1.get(i));
                p1t.remove(i);
                p(p1t, p2t);
                last = p1.get(i);
            }
            
        }
    }
    
    public List <Integer> clone(List <Integer> l)
    {
    	List <Integer> r = new ArrayList <Integer> ();
    	r.addAll(l);
    	return r;
    }
    
    
    public boolean exist(List <Integer> l)
    {
        return false;
        /*for(int i = 0 ; i < result.size() ; i ++)
        {
            if(l.equals(result.get(i)))
                return true;
        }
        return false;*/
    }
}
